/**
 * https://leetcode.cn/problems/partition-equal-subset-sum/submissions/590292978/
 * 416.分割等和子集
 * medium 2024.12.30
 * 记忆化回溯
 */

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n=nums.size();
        int sum=0;
        for(auto &x:nums)
            sum+=x;
        if(sum%2)
            return false;
        int target=sum/2;
        vector<bool> dp(target+1,false);
        dp[0]=true;
        for(int i=0;i<n;++i){
            for(int j=target;j>=nums[i];--j){
                if(dp[j-nums[i]]){
                    dp[j]=true;
                }
            }
        }
        return dp[target];
    }
};